/**
 * 
 */
package com.gwcloud.leetcode.tags.tree;

import com.gwcloud.leetcode.common.datastructure.TreeNode;

/**
 * @ClassName   : Leetcode105 
 * @author      : ganwei 
 * @date        : 2020年5月5日
 * @Description : Leetcode105 从前序与中序遍历序列构造二叉树
 */
public class Leetcode0105 {
    /**
     * -从树算法的架构上看，前序遍历构建（递归方式）
     */
	public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0 || preorder.length != inorder.length) {
            return null;
        }
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }
    
	public TreeNode build(int[] preorder, int pStart, int pEnd, int[] inorder, int iStart, int iEnd){
		if(pStart > pEnd || iStart > iEnd) {
			return null;
		}
		TreeNode node = new TreeNode(preorder[pStart]);
		int index = 0;
		while(inorder[iStart + index] != preorder[pStart]) {
			index++;
		}
		//构建左子树
		node.left = build(preorder,pStart+1,pStart+index,inorder,iStart,iStart+index-1);
		//构建右子树
		node.right = build(preorder,pStart+index+1,pEnd,inorder,iStart+index+1,iEnd);
		
		return node;
	}

    public static void main(String[] args){
    	
    }
}
